package com.graph;

import java.util.*;

public class Solution1129 {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[] redList = new List[n];
        List<Integer>[] blueList = new List[n];
        for (int i = 0; i < n; i++) redList[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) blueList[i] = new ArrayList<>();
        for (int[] redEdge : redEdges) redList[redEdge[0]].add(redEdge[1]);
        for (int[] blueEdge : blueEdges) blueList[blueEdge[0]].add(blueEdge[1]);

        int[] redRes = new int[n];
        int[] blueRes = new int[n];
        Arrays.fill(redRes, Integer.MAX_VALUE);
        Arrays.fill(blueRes, Integer.MAX_VALUE);
        redRes[0] = 0;
        blueRes[0] = 0;

        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        queue.add(new int[]{0, 1});
        int dis = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            dis++;
            while (size > 0) {
                int[] curArr = queue.removeFirst();
                int cur = curArr[0];
                if (curArr[1] == 0) {
                    for (int x : redList[cur]) {
                        if (dis < redRes[x]) {
                            redRes[x] = dis;
                            queue.add(new int[]{x, 1});
                        }
                    }
                } else {
                    for (int x : blueList[cur]) {
                        if (dis < blueRes[x]) {
                            blueRes[x] = dis;
                            queue.add(new int[]{x, 0});
                        }
                    }
                }
                size--;
            }
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = Math.min(redRes[i], blueRes[i]);
            if (res[i] == Integer.MAX_VALUE) res[i] = -1;
        }
        return res;
    }
}
